import java.util.Arrays;
import java.util.PriorityQueue;

public class FindRightInterval {

    public int[] findRightInterval1(int[][] intervals) {
        PriorityQueue<Integer> heap1 = new PriorityQueue<>((a, b) -> intervals[a][1] - intervals[b][1]);
        PriorityQueue<Integer> heap2 = new PriorityQueue<>((a, b) -> intervals[a][0] - intervals[b][0]);
        for (int i = 0; i < intervals.length; i++) {
            heap1.add(i);
            heap2.add(i);
        }
        int[] ans = new int[intervals.length];
        Arrays.fill(ans, -1);
        while (!heap1.isEmpty() && !heap2.isEmpty()) {
            if (intervals[heap2.peek()][0] >= intervals[heap1.peek()][1]) {
                ans[heap1.peek()] = heap2.peek();
                heap1.poll();
            } else {
                heap2.poll();
            }
        }
        return ans;
    }

    public int[] findRightInterval(int[][] intervals) {
        int n = intervals.length;
        int[][] temp = new int[n][n];
        for (int i = 0; i < intervals.length; i++) {
            temp[i][0] = intervals[i][0];
            temp[i][1] = i;
        }
        Arrays.sort(temp, (a, b) -> a[0] - b[0]);
        int[] ans = new int[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            int l = 0;
            int r = intervals.length - 1;
            int target = -1;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (temp[mid][0] >= intervals[i][1]) {
                    target = temp[mid][1];
                    r = mid - 1;
                } else l = mid + 1;
            }
            ans[i] = target;
        }
        return ans;
    }
}
